#include <iostream>
#include <map>
#include <vector>

using namespace std;

// size_t n = 4;
// size_t step = 2;
// size_t sudoku[4][4] =
//     // {{3, 4, 0, 2},
//     //  {0, 0, 0, 0},
//     //  {0, 0, 0, 0},
//     //  {2, 0, 0, 3}};
//     // {{0, 4, 0, 0},
//     //  {3, 0, 0, 0},
//     //  {0, 0, 4, 0},
//     //  {0, 2, 3, 0}};
//     {{0, 4, 0, 0},
//      {0, 0, 0, 4},
//      {1, 0, 0, 0},
//      {0, 0, 3, 0}};

size_t gtimes = 0U;
size_t gstep = 3U;
size_t gn = gstep * gstep;
size_t gsudoku[9][9] =
    // {{0, 0, 7,  0, 0, 8,  9, 0, 6},
    //  {0, 8, 4,  0, 5, 1,  7, 0, 0},
    //  {0, 0, 6,  0, 0, 0,  5, 0, 0},

    //  {0, 1, 0,  0, 8, 0,  3, 9, 0},
    //  {5, 0, 0,  0, 6, 0,  0, 0, 4},
    //  {0, 4, 3,  5, 0, 2,  0, 7, 0},

    //  {0, 0, 1,  0, 0, 6,  8, 0, 0},
    //  {0, 0, 5,  8, 2, 0,  1, 6, 0},
    //  {3, 0, 8,  9, 0, 0,  4, 0, 0}};
    {{0, 0, 0, 0, 1, 0, 0, 4, 7},
     {0, 0, 0, 0, 0, 0, 0, 0, 3},
     {5, 0, 7, 8, 0, 3, 0, 0, 0},

     {0, 0, 0, 9, 0, 2, 0, 5, 0},
     {0, 8, 0, 0, 0, 0, 0, 0, 0},
     {2, 7, 0, 5, 0, 0, 0, 8, 6},

     {0, 2, 0, 0, 5, 0, 0, 0, 0},
     {0, 0, 1, 0, 0, 6, 0, 7, 0},
     {3, 5, 0, 7, 0, 0, 4, 9, 0}};
    // {{0, 0, 0, 0, 0, 0, 0, 0, 0},
    //  {0, 0, 0, 0, 0, 0, 0, 0, 0},
    //  {0, 0, 0, 0, 0, 0, 0, 0, 0},

    //  {0, 0, 0, 0, 0, 0, 0, 0, 0},
    //  {0, 0, 0, 0, 0, 0, 0, 0, 0},
    //  {0, 0, 0, 0, 0, 0, 0, 0, 0},

    //  {0, 0, 0, 0, 0, 0, 0, 0, 0},
    //  {0, 0, 0, 0, 0, 0, 0, 0, 0},
    //  {0, 0, 0, 0, 0, 0, 0, 0, 0}};

void print(map<pair<size_t, size_t>, size_t> &sdk, const size_t n)
{
    for (size_t i = 0; i < n; i++)
    {
        if (i%gstep == 0U)
            cout << endl;
        
        for (size_t j = 0; j < n; j++)
        {
            if (j%gstep == 0U)
                cout << " ";
            cout << sdk[{i,j}] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

void split(map<pair<size_t,size_t>,size_t>& sdk
    ,map<size_t, vector<size_t> >& rows
    ,map<size_t, vector<size_t> >& columns
    ,map<pair<size_t, size_t>, vector<size_t> >& zones)
{
    for (size_t i = 0; i < gn; i++)
    {
        for (size_t j = 0; j < gn; j++)
        {
            rows[i].push_back(sdk[{i, j}]);
            columns[i].push_back(sdk[{j, i}]);
            zones[{i / gstep, j / gstep}].push_back(sdk[{i, j}]);
        }
    }
}

bool check(map<pair<size_t,size_t>,size_t>& sdk)
{
    map<size_t, vector<size_t>> rows, columns;
    map<pair<size_t, size_t>, vector<size_t>> zones;
    split(sdk, rows, columns, zones);

    for (auto row : rows)
    {
        map<size_t, bool> vals;
        size_t count = 0U;
        for (auto item : row.second)
        {
            if (item != 0U)
            {
                count++;
                vals[item] = false;
            }
        }
        if (vals.size() < count)
        {
            return false;
        }
    }

    for (auto col : columns)
    {
        map<size_t, bool> vals;
        size_t count = 0U;
        for (auto item : col.second)
        {
            if (item != 0U)
            {
                count++;
                vals[item] = false;
            }
        }
        if (vals.size() < count)
        {
            return false;
        }
    }

    for (auto zone : zones)
    {
        map<size_t, bool> vals;
        size_t count = 0U;
        for (auto item : zone.second)
        {
            if (item != 0U)
            {
                count++;
                vals[item] = false;
            }
        }
        if (vals.size() < count)
        {
            return false;
        }
    }

    return true;
}

bool calculate(map<pair<size_t,size_t>,size_t>& sdk
    , pair<pair<size_t, size_t>, vector<size_t> >& unknown
    )
{
    gtimes++;
    bool cont = true;
    unknown.second.clear();
    map<pair<size_t, size_t>, size_t> tsdk = sdk;

    while (cont)
    {
        map<pair<size_t, size_t>, vector<size_t>> vals;
        map<size_t, vector<size_t>> rows, columns;
        map<pair<size_t, size_t>, vector<size_t>> zones;
        split(tsdk, rows, columns, zones);

        for (size_t i = 0; i < gn; i++)
        {
            for (size_t j = 0; j < gn; j++)
            {
                if (tsdk[{i, j}] == 0)
                {
                    for (size_t x = 0; x < gn; x++)
                    {
                        size_t val = x + 1;
                        bool legal = true;
                        // row
                        for (auto rv : rows[i])
                        {
                            if (rv == val)
                            {
                                legal = false;
                                break;
                            }
                        }
                        // column
                        if (legal)
                        {
                            for (auto cv : columns[j])
                            {
                                if (cv == val)
                                {
                                    legal = false;
                                    break;
                                }
                            }
                        }
                        // zones
                        if (legal)
                        {
                            for (auto zv : zones[{i / gstep, j / gstep}])
                            {
                                if (zv == val)
                                {
                                    legal = false;
                                    break;
                                }
                            }
                        }
                        if (legal)
                        {
                            vals[{i, j}].push_back(val);
                        }
                    }
                    // Error
                    if (vals[{i, j}].empty())
                    {
                        return false;
                    }
                }
            }
        }

        // Print
        for (size_t i = 0; i < gn; i++)
        {
            for (size_t j = 0; j < gn; j++)
            {
                if (vals[{i, j}].empty())
                {
                    cout << "-";
                }
                else
                {
                    for (auto item : vals[{i, j}])
                    {
                        cout << item;
                    }
                }
                cout << " ";
            }
            cout << endl;
        }
        cout << endl;

        cont = false;
        for (size_t i = 0; i < gn; i++)
        {
            for (size_t j = 0; j < gn; j++)
            {
                if (vals[{i, j}].size() == 1)
                {
                    tsdk[{i, j}] = vals[{i, j}][0];
                    cont = true;
                }
                else if (vals[{i, j}].size() > 1)
                {
                    unknown = {{i, j}, vals[{i, j}]};
                }
            }
        }
    }

    if (check(tsdk))
    {
        sdk = tsdk;
        return true;
    }
    else
    {
        return false;
    }
}

bool recursive(map<pair<size_t,size_t>,size_t>& sdk)
{
    pair<pair<size_t, size_t>, vector<size_t> > unknown;
    bool res = calculate(sdk, unknown);
    cout << "calculate " << gtimes << endl;
    print(sdk, gn);
    if (res)
    {
        if (unknown.second.empty())
        {
            cout<<"Done"<<endl;
            return true;
        }
        else
        {
            for (auto item : unknown.second)
            {
                map<pair<size_t,size_t>,size_t> ttsdk = sdk;
                ttsdk[unknown.first] = item;
                if (recursive(ttsdk))
                {
                    sdk = ttsdk;
                    return true;
                }
            }
            return false;
        }
    }
    else
    {
        return false;
    }
}

int main()
{
    map<pair<size_t,size_t>,size_t> sdk;
    for (size_t i = 0; i < gn; i++)
    {
        for (size_t j = 0; j < gn; j++)
        {
            sdk[{i,j}] = gsudoku[i][j];
        }
    }

    if (!recursive(sdk))
    {
        cout<<"Sudoku is no solution"<<endl;
    }

    return 0;
}